// 不用任何算术运算，只用位运算实现加减乘除
// 代码实现中你找不到任何一个算术运算符
// 测试链接 : https://leetcode.cn/problems/divide-two-integers/
public class BitOperationAddMinusMultiplyDivide {


    public static void main(String[] args) {
        BitOperationAddMinusMultiplyDivide b = new BitOperationAddMinusMultiplyDivide();

        b.test();
    }
    public void test() {
        System.out.println(divide(MIN,-2));
        System.out.println(divide(MIN,2));
    }
    public static int MIN = Integer.MIN_VALUE;
    public int add(int a, int b) {  //加法：a异或b(相当于a+b没有进位)加上a&b<<1(相当于a加b的进位)
        int ans = a;
        while( b != 0) {
            ans ^= b;
            b = (a & b) << 1;  //加上进位
            a = ans;
        }
        return  ans;
    }


    public int minus(int a, int b) {  //减法：a+(-b)
        return add(a,neg(b));
    }

    public int neg(int n) { //返回-n
        return add(~n,1);
    }

    public  int multiply(int a, int b) {  //乘法
        int ans = 0;
        while ( b != 0) {
            if((b & 1) == 1){
                ans = add(ans,a);
            }
            a <<= 1;
            b >>>=1;
        }
        return ans;
    }

    public  int div(int a, int b) {
        int x = a < 0 ? neg(a) : a;  //如果ab有负数先全变成正数
        int y = b < 0 ? neg(b) : b;

        int ans = 0;
        for(int i = 30; i >= 0; i = minus(i,1)) {
            if( (x >> i) >= y ) {
                ans |= 1 << i;
                x = minus(x,y << i);
            }
        }

        return a<0 ^ b<0 ? neg(ans) : ans;  //ab符号不一样异或则为true
    }

    public int divide(int a, int b) {
        if( a == MIN && b == MIN) { //两个都为最小值
            return 1;
        }
        if( a != MIN && b != MIN) {  //正常范围
            return div(a,b);
        }

        if(b == MIN) {  //除数是最小值
            return 0;
        }

        if (b == neg(1)) {
            return Integer.MAX_VALUE; // a是整数最小，b是-1，返回整数最大，
        }

        if( b > 0) {
            return div(add(a,b),b) -1 ;
        }else {
            return div(minus(a,b),b) +1 ;
        }
    }
}
